package 蓝桥算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class day08 {

        public List<List<Integer>> ThreeSum ( int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > 0) {
                    return result;
                }
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[left] + nums[right];
                    if (sum > 0) {
                        right--;
                    } else if (sum < 0) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;//完成符合条件的一种后才进行正规遍历
                    }
                }
            }
            return result;
        }
        public List<List<Integer>> FourSum(int[] nums,int target){
            List<List<Integer>> result=new ArrayList<>();
            Arrays.sort(nums);
            for (int i=0;i<nums.length;i++){
                if(nums[i]>=0&&nums[i]>target){
                    break;
                }
                if(i>0&&nums[i]==nums[i-1]){
                    continue;
                }//实现减枝
                for(int j=i+1;j<nums.length;j++){//防止重复遍历
                    if(nums[j]+nums[i]>=0&&nums[j]+nums[i]>=target){
                        break;
                    }
                    if(j>0&&nums[j]==nums[j-1]){
                        continue;
                    }
                    int left=i+1;
                    int right=nums.length-1;
                    while(left<right){
                        int sum=nums[i]+nums[j]+nums[left]+nums[right];
                        if(sum>target){
                            right--;
                        }
                        else if(sum<target){
                            left++;
                        }
                        else {
                            result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                            left++;
                            right--;
                        }
                    }
                }
            }
            return result;
        }
    public static void main(String[] args) {
        int[] nums={-1,3,4,2,-2,-2,-6,7,4,3};
       /* List<List<Integer>>list=new ArrayList<>();*/
        day08 x=new day08();
      /*  list=x.ThreeSum(nums);
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i));
        }*/
        List<List<Integer>>list1=new ArrayList<>();
        list1=x.FourSum(nums,1);
        for(int i=0;i<list1.size();i++){
            System.out.print(list1.get(i));
        }


    }
}
